1. Field of the Invention
The present invention relates to a method of estimating crosstalk noise in high-speed VLSI interconnects and, more particularly, to a method of using moment computations of lumped coupled RLC-tree models and project-based model-order reduction techniques.
2. Description of Related Art
Modern technological trends have caused interconnect modeling to have attracted considerable attention in high-speed VLSI designs. Owing to these designs with performance considerations, increasing clock frequency, shorter rising times, higher density of wires, and using low-resistivity materials, on-chip inductance effects can no longer be ignored in interconnect models. Furthermore, the importance of coupling inductance effects has grown continuously since nanometer technology has emerged over the last few years. It has been observed that crosstalk noise estimations made by considering inductance effects may yield more pessimistic results than those made without considering coupling inductance effects, as discussed in C. K. Cheng, J. Lillis, S. Lin, and N. H. Chang, Interconnect Analysis and Synthesis, John Wiley and Sons Inc., 2000. Such estimation errors follow from two main reasons: (1) more and longer wires in parallel increase the capacitive coupling, leading to large current changes on the victim nets, and (2) increasing self inductance worsens overshooting spikes on aggressor nets, and may worsen noise on the victim nets. For the above practical considerations, interconnect models shall be extended to be coupled RLC trees while considering the inductance effects.
A common manner of estimating crosstalk noise is implemented by simulating circuit-level VLSI interconnects. Although the results are very accurate, the computational complexity is excessive, especially for large-scale interconnect simulations. An alternative approach, called model-order reduction methods, has recently emerged to solve the problem, as disclosed in L. T. Pillage and R. A. Robrer, “Asymptotic waveform evaluation for timing analysis,” IEEE Trans. Computer-Aided Design, vol. 9, no. 4, pp. 352–366, 1990; P. Feldmann and R. W. Freund, “Efficient linear circuit analysis by Pade approximation via the Lanczos process,” IEEE Trans. Computer-Aided Design, vol. 14, no. 5, 1995, and A. Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macromodeing algorithm,” IEEE Trans. Computer-Aided Design, vol. 17, no. 8, pp. 645–653, 1998. Rather than directly estimating the crosstalk waveform of the original interconnects, the crosstalk noise of the reduced-order system is estimated. However, the computational cost is still too high for a noise optimization problem even though model-order reduction methods have reduced the cost, as disclosed in A. Devgan, “Efficient coupled noise estimation for on-chip interconnects,” in Porc. ICCAD, 1997, pp. 147–151; and M. Kuhlmann and S. S. Sapatnekar, “Exact and efficient crosstalk estimation,” IEEE Trans. Computer-Aided Design, vol. 20, no. 7, pp. 858–866, 2001.
A consensus has emerged that of the many model-order reduction techniques, the moment matching approach seems to be the most viable for estimating interconnect crosstalk noise. For computational efficiency, traditional models for estimating noise in coupled RC trees have been developed, including the one-pole model (1P) (as disclosed in A. Vittal, L. H. Chen, M. Marek-Sadowska., K. P. Wang, and S. Yang, “Crosstalk in VLSI interconnects,” IEEE Trans. Computer-Aided Design, vol. 18, pp. 1817–1824, 1999; and A. Vittal and M. Marek-Sadowska, “Crosstalk reduction for VLSI,” IEEE Trans. Computer-Aided Design, vol. 16, pp. 290–298, 1997), the modified one-pole model (M1P) (as disclosed in Q. Yu and E. S. Kub, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772–788, 2001), the two-pole model (2P) (as discussed in M. Kuhlmann and S. S. Sapatnekar, “Exact and efficient crosstalk estimation,” IEEE Trans. Computer-Aided Design, vol. 20, no. 7, pp. 858–866, 2001; and Q. Yu and E. S. Kuh, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772–788, 2001), the stable two-pole model (S2P) (as disclosed in E. Acar, A. Odabasioglu, M. Celik, and L. T. Pileggi, “S2P: A stable 2-pole RC delay and coupling noise metric,” in Proc. 9th Great Lakes Symp. VLSI, March 1999, pp. 60–63), and the guaranteed stable three-pole model (S3P) (as discussed in Q. Yu and E. S. Kuh, “Moment computation of lumped and distributed coupled RC trees with application to delay and crosstalk estimation,” Proceedings of the IEEE, vol. 89, no. 5, pp. 772–788, 2001). Unlike the general model-order reduction methods, the techniques simply estimate the peak value of crosstalk noise and the time at which it peaks rather than evaluating the waveform of crosstalk noise. Also, U.S. Pat. Nos. 5,481,695; 5,535,133; 5,555,506; 5,568,395; 5,596,506; 6,018,623; 6,029,117; and 6,405,348 have disclosed the techniques about the crosstalk noise estimations. However, since the interconnect crosstalk noise may have a non-monotonic response waveform, these models seem to be unsuitable for capturing the essential nature of such crosstalk noise.
Recently, the delay and noise formulae by considering self inductances and mutual inductances have been disclosed in Y. Cao, X. Huang, D. Sylvester, N. Chang, and C. Hu, “A new analytical delay and noise model for on-chip RLC interconnect,” in Proc. IEDM 2000, 2000, pp. 823–826. However, their model is restricted to two parallel lines. The analytical delay and overshooting formulae for coupled RLC lines have been disclosed in M. H. Chowdhury, Y. I. Ismail, C. V. Kashyap, and B. L. Krauter, “Performance analysis of deep sub micron VLSI circuits in the presence of self and mutual inductance,” in Proc. ISCAS 2002, 2002, pp. 197–200. However, issues concerning inductive crosstalk noise analysis have still not yet been studied. Furthermore, by exploring the special nature of RLC-tree structures, recursive algorithms for computing system moments with linear order have been developed, for example, by C. L. Ratzlaff and L. T. Pillage, “RICE: rapid interconnect circuit evaluation using AWE,” IEEE Trans. Computer-Aided Design, vol. 13, no. 6, pp. 763–776, 1994 and Q. Yu and E. S. Kuh, “Exact moment matching model of transmission lines and application to interconnect delay estimation,” IEEE Trans. VLSI syst., vol. 3, no. 2, pp. 311–322, 1995, independently. Moment models of general transmission lines were presented in Q. Yu, E. S. Kuh, and T. Xue, “Moment models of general transmission lines with application to interconnect analysis and optimization,” IEEE Trans. VLSI syst., vol. 4, no. 4, pp. 477–494, 1996. However, these studies did not mention moment computations for coupled RLC trees.
The technique, “Crosstalk estimated in high-speed VLSI interconnect using coupled RLC-tree models”, which is proposed in Proc. 2002 IEEE Asia Pacific Conference on Circuits and Systems, comprised the initial research. Although the moment computation formulae for coupled REC trees have been developed, the technique about efficiently constructing the crosstalk estimation model was not provided. Also, the stability of the model was still not analyzed.